package Acwing.搜索与图论;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Title: dijkstraFindMinValue1
 * @Author 贾金博
 * @Package Acwing.搜索与图论
 * @Date 2025/4/11 下午6:52
 * @description: Dijkstra求最短路1
 */
public class dijkstraFindMinValue1 {

    private static int n;
    private static int m;
    private static long[] dis; // 这里相加之后 可能出溢出 注意要去开 long
    private static boolean[] st;
    private static int[][] a;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 总共的节点数
        m = sc.nextInt(); // 总共的边数
        a = new int[n + 10][n + 10];
        dis = new long[n + 10];
        st = new boolean[n + 10]; // 表示当前这个点有没有被确定

        init();

        for(int j = 1; j <= m; j ++ ) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            a[x][y] = Math.min(a[x][y], z); // 注意的是 有向图 如果发生重边的情况则保留最短的一条边
        }

        dijkstra();

        if(dis[n] == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(dis[n]);
        }


    }

    // 数组的初始化
    public static void init() {
        Arrays.fill(dis, Integer.MAX_VALUE); // 类似于 c++ 里面的 memset
        dis[1] = 0; // 起始点初始化为 0
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= n; j ++ ) {
                a[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    // 朴素版的dijkstra算法
    public static void dijkstra() {

        for(int i = 1; i <= n; i ++ ) {
            int t = -1;
            for(int j = 1; j <= n; j ++ ) {
                if(!st[j] && (t == -1 || dis[t] > dis[j] ) ) {
                    t = j;
                }
            }
            st[t] = true;

            // 拿这个点去更新其他的点
            for(int j = 1; j <= n; j ++ ) {
                dis[j] = Math.min(dis[j], dis[t] + a[t][j]);
            }
        }
    }
}
